'''VERSION 1.0'''
import networkx as nx
import sys
import pp
import time


def distribute(nitems, nprocs=None):
    """
        :param nitems: the number of items to be distributed
        :type nitems: int
        :param nprocs: the number of processors available
        :type nprocs: int
        :returns: a list of index tuples (imin, imax)
        defining the slices of the input sequence
        to be handled by each processor
        :rtyoe: list
        """
    if nprocs is None:
        nprocs = default_nprocs
    nitems_per_proc = (nitems+nprocs-1)/nprocs
    return [(i, min(nitems, i+nitems_per_proc))
            for i in range(0, nitems, nitems_per_proc)]

def divide_and_conquer(n,ts):
    if n == 0:
        return [0]
    if n < ts:
        return [ts]
    step = round(n/ts)
    if step == 0:
        step = 1
    divs = [int(i*step) for i in range(ts) if (i*step) < n]
    divs.append(n)
    return divs

'''
    Parallelized function
'''
def process_itemsets(items,border,faces):
    results = set([])
    belim = set([])
    bplus = set([])
    for item in items:
        # calculate candidates
        candidates = set([])
        for b in border:
            a = item & b
            if a not in candidates:
                candidates.add(a)
        
        # candidates = order_bins(candidates) SEEMS NOT NECESSARY
        
        # CHECK CANDIDATES' FACES
        for c in candidates:
            f =  faces.get(c,0)
            if item & f == 0:
                results.add((item,c))
                if c in border:
                    belim.add(c)
                faces[c] = f | (item & (item ^ c))
                bplus.add(item)
    return bplus,belim,faces,results


def order_bins(cands):
    b = [(sum([int(j) for j in bin(i)[2:]]),i) for i in cands]
    b.sort(reverse=True)
    return [i[1] for i in b]

class Concept:
    def __init__(self,intent,id):
        self.intent = intent
        self.support = 0
        self.id = id
        self.bin_intent()
    
    def bin_intent(self):
        self.bin = 0
        for i in intent:
            self.bin += 1 << int(i)

def initialize_node(conc,g):
    g.add_node(conc.id, intent=conc.bin,intt=str(conc.intent).replace('[','').replace(']','').replace("'",'').replace(' ',''),support = conc.support)

path = sys.argv[2]

file = open(path,'r')

# the output lattice is modeled as a directed graph
g = nx.DiGraph()
# inverted index from binary representations to the formal concepts
inv_idx = {} 
# Level-wise ordered concepts 
latidx = {} 

'''
    BEGIN READING ITEMSETS
'''
for line in file:
    line = line.replace('\n','')
    intent = line.split()
    sup = intent[len(intent)-1]
    intent = intent[:len(intent)-1]
    conc = Concept(intent,len(g.node))
    conc.support = int(sup.replace('(','').replace(')',''))
    if len(intent) not in latidx:
        latidx[len(intent)] = []
    latidx[len(intent)].append(conc.bin)
    initialize_node(conc,g)
    inv_idx[conc.bin] = conc

# Concepts have to be processed from lower to higher levels
nums = latidx.keys()
nums.sort()

ppservers = ()

if len(sys.argv) > 2:
    ncpus = int(sys.argv[1])
    # Creates jobserver with ncpus workers
    job_server = pp.Server(ncpus, ppservers=ppservers)
else:
    # Creates jobserver with automatically detected number of workers
    job_server = pp.Server(ppservers=ppservers)

print "Starting pp with", job_server.get_ncpus(), "workers"

start_time = time.time()

border = set([0])
faces = {}
i = 0
nproc = {}
for n in nums:
    # each layers have to be processed sequentially
    if n != 0:
        # a layer is divided in several subtask (4 in this case)
        breaks = ncpus
        if len(latidx[n]) < 80:
            breaks = 1
        calcul_time_0 = time.time()
        divs = divide_and_conquer(len(latidx[n]),breaks)
    #slices = distribute(len(latidx[n],ncpus)
        jobs =  [job_server.submit(process_itemsets, (latidx[n][divs[d]:divs[d+1]],border,faces)) for d in range(len(divs)-1)]
        nproc[n] = len(jobs)
        job_server.wait()
        calcul_time_1 = time.time()
        job_server.wait()
        # after all jobs in the layer are finished, data is integrated
        for j in jobs:
            bp,bm,fs,rs = j()
            border.update(bp)
            for b in bm:
                border.discard(b)
            for c in fs:
                faces[c] = faces.get(c,0) | fs[c]
            for arc in rs:
                g.add_edge(inv_idx[arc[0]].id,inv_idx[arc[1]].id)
        int_time = time.time() - calcul_time_1
        calc_time = calcul_time_1 - calcul_time_0
        print "Layer",n,':',nproc[n],'jobs',(calc_time),'/',len(latidx[n]),'||',(int_time),'==',(calc_time + int_time)

job_server.print_stats()
for n in g.nodes():
    del g.node[n]['intent'] # Intent contains too much information, is eliminated from the output
nx.write_gml(g,"lattice.gml")
ug = g.to_undirected()
